In this work, we propose a two-stage approach to strengthen piecewiseMcCormick relaxations for mixed-integer nonlinear programs (MINLP) withmulti-linear terms. In the first stage, we exploit Constraint Programing (CP)techniques to contract the variable bounds. In the second stage we partitionthe variables domains using a dynamic multivariate partitioning scheme. Insteadof equally partitioning the domains of variables appearing in multi-linearterms, we construct sparser partitions yet tighter relax- ations by iterativelypartitioning the variable domains in regions of interest. This approachdecouples the number of partitions from the size of the variable domains, leadsto a significant reduction in computation time, and limits the number of binaryvariables that are introduced by the partitioning. We demonstrate theperformance of our algorithm on well-known benchmark problems from MINLPLIB anddiscuss the computational benefits of CP-based bound tightening procedures.
展开▼
